package cn.fxzhang.leetcode.contest.weekd50;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 5720. 使字符串有序的最少操作次数
 *
 * 类型：数学组合排列
 * 题解：
 * 时间复杂度：O(N)
 * 空间复杂度：O(N)
 *
 * 提交记录(0/0)：
 * 执行用时: 0 ms, 击败了100.00%
 * 内存消耗: 37.8 MB, 击败了77.84%
 * todo 本题未通过
 * 【困难】通过次数116,961提交次数267,848
 * @author 张晓帆
 * @date 2021/4/17
 */
public class P5720_Minimum_Number_Of_Operations_To_Make_String_Sorted {

    public int makeStringSorted(String s) {
        long mod = (long) (1e9+7);
        int n = s.length();
        long t = 1;
        long ans = 0;
        for (int i=n-2; i>=0; i--){
            char c = s.charAt(i);

            long k = t;
            int lessCount = 0;
            Map<Integer, Integer> map = new HashMap<>();
            for (int j=i+1; j<n; j++){
                char c1 = s.charAt(j);
                Integer delta = c-c1;
                if (c > c1) {
                    Integer count = map.get(delta);
                    if (count == null){
                        map.put(delta, 1);
                    } else{
                       map.put(delta, ++count);
                       k /= count;
                    }
                }
            }
            Set<Integer> keySet = map.keySet();
            int b = 1;
            for (int key: keySet){
                b = b*map.get(key);
            }
            // ans = (ans+key*k) % mod;
            t = t*(n-i)%mod;
        }
        return (int)ans;
    }
}
